import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class test6 {
    /*
        以数组 intervals 表示若干个区间的集合，其中单个区间为
        intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，
        该数组需恰好覆盖输入中的所有区间 。
    **/
    public static void main(String[] args) {
        // 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18},{9,15}};
        System.out.println(Arrays.deepToString(merge(intervals)));
    }

    public static int[][] merge(int[][] intervals) {
        // 对数组进行排序，以starti升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];

            if (interval[0] <= currentEnd) {
                // 如果有重叠，更新currentInterval的end
                currentInterval[1] = Math.max(currentEnd, interval[1]);
            } else {
                // 没有重叠，添加新的区间到结果列表
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}


